package com.zzw.algorithm.treenode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Stack;

public class TreeNodeTest {

	public List<Integer> preoderTraversal(TreeNode root){
		List<Integer> result = new ArrayList<>();
		if(root == null)
			return result;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode node = stack.pop();
			result.add(node.getVal());
			if(node.right != null){
				stack.push(node.right);
			}
			if(node.left != null){
				stack.push(node.left);
			}
		}
		return result;
	}
	
	public List<Integer> postTraversal(TreeNode root){
		List<Integer> result = new ArrayList<>();
		if(root == null)
			return result;
		Deque<TreeNode> stack = new ArrayDeque<>();
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode node = stack.pop();
			result.add(node.getVal());
			if(node.left != null){
				stack.push(node.left);
			}
			if(node.right != null){
				stack.push(node.right);
			}
		}
		Collections.reverse(result);
		return result;
	} 
	
	public List<Integer> inorderTraversal(TreeNode root){
		List<Integer> result = new ArrayList<>();
		if(root == null)
			return result;
		Deque<TreeNode> stack = new ArrayDeque<>();
		
		while(root != null || !stack.isEmpty()){
			while(root != null){
				stack.push(root);
				root = root.left;
			}
			TreeNode node = stack.pop();
			result.add(node.getVal());
			root = node.right;
		}
		return result;
	} 
}
